﻿#include <iostream>
using namespace std;

void sortR(int w[], int v[], int n) {
	int i, j, index, vTemp, wTemp;
	for(i = 0; i < n - 1; i++) {
		index = i;
		for(j = i + 1; j < n; j++) {
			if(v[j] / w[j] > v[index] / w[index]) {
				index = j;
			}
		}
		if(index != i) {
			vTemp = v[i];
			wTemp = w[i];
			v[i] = v[index];
			w[i] = w[index];
			v[index] = vTemp;
			w[index] = wTemp;
		}
	}
}

int knapSack(int w[], int v[], int n, int c) {
	int i;
	sortR(w, v, n);					//改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列
	double x[10] = {0};				//物品可按部分装入
	int maxValue = 0;
	for(i = 0; w[i] < c; i++) {
		x[i] = 1;					//将物品i装入背包
		maxValue += v[i];
		c = c - w[i];				//背包剩余容量
	}
	x[i] = (double)c / w[i];		//物品i装入一部分
	maxValue += x[i] * v[i];

	return maxValue;				//返回背包获得的价值
}

int main() {
	const int n = 3;
	int c = 50;
	//int w[n] = {20, 30, 10};
	//int v[n] = {60, 120, 50};
	int w[n] = {10, 30, 20};
	int v[n] = {50, 120, 60};
	cout << knapSack(w, v, n, c) << endl;

	system("pause");
	return 0;
}